Shadow mapping is a technique, generally traced back to the paper of Williams, “Casting curved shadows on curved surfaces,” SIGGRAPH '78 Proc. 5th Annual Conf. on Computer Graphics, pp. 270-74 (1978) (incorporated herein by reference), used to determine where shadows lie in 3D computer graphics on the basis of knowledge of the source and direction of light illuminating a 3D scene. In traditional shadow mapping, each pixel is tested as to whether it is visible from the light source and thus illuminated by it, and, if not, the pixel is designated as to be shadowed.
As described, shadow mapping is based upon 3D data. However, in the context of geographic information systems (GIS), 3D data may not be available. Indeed, it would be highly desirable to provide the capability to estimate shadows cast by any illumination source, either indoors or outdoors, where the available data might be surface elevation, LIDAR, point cloud, or partial surface data, and where full side wall data may not be available. In particular, data relevant to side walls of man-made structures, or to naturally occurring slopes in hilly or mountainous terrain, are largely absent from elevation data.
For purposes of illustration, FIG. 1A shows a three-dimensional object, namely cube 10, and how that cube might be represented in 2.5D elevation data. A top view of cube 10, shown in FIG. 1B, depicts four resolution cells 12, where each cell is characterized by an elevation point 14, and where the elevation points as a function of position—on the surface of the Earth, for example, comprise a set of elevation data. Elevation data, however, provide no information about sides of the three-dimensional object 10. The result of the absence of data regarding sides of object 10 is shown in FIG. 1C where light 16 from source 15 is shadowed by object 10, however the calculated shadow 17 cast by object 10 does not include the intervening region 19 where a calculated shadow is missing.
Moreover, in addition to the absence of full 3D geometric data, another daunting feature of GIS data sets is the very large quantity of data that must be processed, often in a near real-time mode.